package com.frx.sort;

import java.util.Arrays;

/**
 * Created by xurenfeng on 2019/2/19.
 */
public class ShellSort<T extends Comparable<T>> extends Sort<T>{

    public static void main(String[] args){
        ShellSort<Integer> shellSort = new ShellSort<>();
        Integer[] a = {5,11,7,9,2,3,12,8,6,1,4,10};
        System.out.println(Arrays.toString(a));
        shellSort.sort(a);
        System.out.println(Arrays.toString(a));
    }

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        int h = 1;
         while (h < N / 3){
             // 1,4,13,40,...
             h = 3*h+1;
         }

         while (h >= 1){
             for (int i = h;i<N;i++){
                 for(int j = i; j >=h; j-=h){
                     if (less(nums[j],nums[j-h])){
                         swap(nums,j,j-h);
                     }
                 }
                 System.out.println(Arrays.toString(nums));
             }
             System.out.println("-----------------------------");

             h = h/3;
         }
    }
}
